package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author lixqw
 * @date 2020/9/3
 */
public class PredictTheWinner468 {

    AtomicInteger sum01 = new AtomicInteger(0);
    AtomicInteger sum02 = new AtomicInteger(0);

    public boolean PredictTheWinner(int[] nums) {
        return predictWinner(nums, 0, nums.length - 1, sum01, sum02);
    }


    public boolean predictWinner(int[] nums, int left, int right, AtomicInteger sum1, AtomicInteger sum2) {
        int tmp = sum1.get();
        if (left > right) return sum01.get() >= sum02.get();
        //先放左边
        sum1.addAndGet(nums[left]);
        boolean b = predictWinner(nums, left + 1, right, sum2, sum1);
        if (b) return true;
        //再放右边
        sum1.set(tmp + nums[right]);
        boolean b1 = predictWinner(nums, left, right - 1, sum2, sum1);
        sum1.set(tmp);
        return b1;
    }

    static class Solution {
        public boolean PredictTheWinner(int[] nums) {
            int length = nums.length;
            int[][] dp = new int[length][length];
            for (int i = 0; i < length; i++) {
                dp[i][i] = nums[i];
            }
            for (int i = length - 2; i >= 0; i--) {
                for (int j = i + 1; j < length; j++) {
                    dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
            return dp[0][length - 1] >= 0;
        }
    }

    public static void main(String[] args) {
        PredictTheWinner468 winner = new PredictTheWinner468();
        Solution solution = new Solution();
        for (int i = 0; i < 0; i++) {
            int[] nums = ArraysUtils.randInts(4);
            System.out.println(ArraysUtils.formatInts(nums) + "\t" + winner.PredictTheWinner(nums) + "\t" + solution.PredictTheWinner(nums));
        }

        int[] nums = {1, 5, 1, 2};
        nums = new int[]{1, 5, 2};
        System.out.println(ArraysUtils.formatInts(nums) + "\t" + winner.PredictTheWinner(nums) + "\t" + solution.PredictTheWinner(nums));

    }
}
